class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        vector<vector<int>> ans;
        int left = 0, cur = nums.size() - 1, right = cur - 1;
        if (nums[left] > 0) {
            return ans;
        }
        if (nums[left] == 0 && nums[cur] == 0) {
            ans.push_back({0, 0, 0});
            return ans;
        }
        while (cur > 0) {
            while (left < right) {
                if (nums[left] + nums[right] < -nums[cur]) {
                    left++;
                }
                if (nums[left] + nums[right] > -nums[cur]) {
                    right--;
                }
                if ((nums[left] + nums[right] == -nums[cur]) &&
                    (left != right)) {
                    ans.push_back({nums[left], nums[right], nums[cur]});
                    right--;
                    left++;
                    while (nums[left - 1] == nums[left]) {
                        left++;
                    }
                    while (nums[right + 1] == nums[right]) {
                        right--;
                    }
                }
            }
            cur--;
            while (nums[cur + 1] == nums[cur]) {
                cur--;
            }
            if (nums[cur] < 0) {
                break;
            }
            left = 0;
            right = cur - 1;
        }
        return ans;
    }
};
